package day_2022_7_to_8.day48;
import java.util.*;
/**
 * @author haomin
 * @date 2022/08/04 18:54
 **/
public class Day20_3_Num15_ThreeSum {
    // 排序 + 循环
    class Solution {
        public List<List<Integer>> res = new ArrayList<>();

        public List<List<Integer>> threeSum(int[] nums) {
            insertSort(nums);
            for(int i = 0;i < nums.length;i++){
                if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
                int k = nums.length-1;

                for(int j = i + 1;j < nums.length;j++){
                    if(j > i+1 && nums[j] == nums[j-1]) continue; // 去重
                    while (j < k && -nums[i] < nums[j] + nums[k]){
                        k--;
                    }
                    if(j == k) break;
                    if(nums[i] + nums[j] == -nums[k]){
                        List<Integer> ret = new ArrayList<>();
                        ret.add(nums[i]);ret.add(nums[j]);ret.add(nums[k]);
                        res.add(new ArrayList<>(ret));
                    }
                }
            }
            return res;
        }
        // 插入排序
        private void insertSort (int[] nums){
            for(int i = 0;i < nums.length;i++){
                for(int j = i;j > 0 && nums[j] < nums[j-1];j--){
                    int temp = nums[j]; nums[j] = nums[j-1]; nums[j-1]=temp;
                }
            }
        }
    }

    // 循环 + map 再次超时
    class Solution2 {
        public List<List<Integer>> res = new ArrayList<>();
        public Map<Integer,Integer> map = new HashMap();
        public List<List<Integer>> threeSum(int[] nums) {
            int[] data = new int[3];
            for (int num : nums) {
                if(map.containsKey(num)) map.replace(num, map.get(num)+1);
                else map.put(num,1);
            }
            for (int i = 0; i < nums.length; i++) {
                for (int j = i+1; j < nums.length; j++) {
                    map.replace(nums[i],map.get(nums[i])-1);
                    map.replace(nums[j],map.get(nums[j])-1);
                    int k = -(nums[i] + nums[j]);
                    if(map.containsKey(k) && map.get(k) != 0){
                        List<Integer> ret = new ArrayList<>();
                        data[0] = nums[i];data[1] = nums[j];data[2] = k;
                        insertSort(data);
                        for (int datum : data) ret.add(datum);
                        if(!res.contains(ret))res.add(new ArrayList<>(ret));
                    }
                    map.replace(nums[i],map.get(nums[i])+1);
                    map.replace(nums[j],map.get(nums[j])+1);
                }
            }
            return res;
        }
        private void insertSort (int[] nums){
            for(int i = 0;i < nums.length;i++){
                for(int j = i;j > 0 && nums[j] < nums[j-1];j--){
                    int temp = nums[j]; nums[j] = nums[j-1]; nums[j-1]=temp;
                }
            }
        }
    }

    // 回溯 超时
    class Solution1 {
        public List<List<Integer>> res = new ArrayList<>();
        public List<Integer> ret = new ArrayList<>();

        public List<List<Integer>> threeSum(int[] nums) {
            insertSort(nums);
            dfs(nums,0,0);
            return res;
        }
        private void dfs(int[] nums, int start, int sum){
            if(ret.size() == 3 && sum == 0 && !res.contains(ret)) {
                res.add(new ArrayList<>(ret));
            }
            for(int i = start;i < nums.length;i++){
                sum+=nums[i];ret.add(nums[i]);
                dfs(nums,i+1,sum);
                sum-=nums[i];ret.remove(ret.size()-1);
            }
        }
        private void insertSort (int[] nums){
            for(int i = 0;i < nums.length;i++){
                for(int j = i;j > 0 && nums[j] < nums[j-1];j--){
                    int temp = nums[j]; nums[j] = nums[j-1]; nums[j-1]=temp;
                }
            }
        }
    }
}